package com.study.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 快速排序
 *
 * @author yyb8152
 * @since 20220826
 **/
public class QuickSort {
    public static void main(String[] args) {
        List<Integer> quickSort = testQuickSort(Arrays.asList(3, 2, 4, 6, 1, 0, 20));
        System.out.println(quickSort);

    }

    public static List<Integer> testQuickSort(List<Integer> numList) {
        Integer pivot = 0;
        List<Integer> left = null;
        List<Integer> right = null;
        List<Integer> sorted = new ArrayList<>(left.size() + right.size());
        ;
        // 基线条件：如果列表中的元素小于2个就不用排序
        if (numList.size() < 2) {
            return numList;
        } else {
            // 选择任意一个元素作为基准值
            pivot = numList.get(0);
            left = new ArrayList<>();
            right = new ArrayList<>();
            for (Integer num : numList.subList(1, numList.size())) {
                // 获取所有小于等于基准值的子数组(不包含基准值)
                if (num <= pivot) {
                    left.add(num);
                    // 获取所有大于基准值的子数组(不包含基准值)
                } else if (pivot < num) {
                    right.add(num);
                }
            }
        }

        for (Integer leftNum : testQuickSort(left)) {
            sorted.add(leftNum);
        }
        sorted.add(pivot);
        for (Integer rightNum : testQuickSort(right)) {
            sorted.add(rightNum);
        }
        return sorted;
    }
}
